package hot100.logos91To100;

/**
 * @author logos
 * date 2025/7/19 13:02
 * @version v1.0
 * @Package hot100.logos91To100
 */
public class logos99 {

    /**
     * 99. 下一个排列
     * https://leetcode.cn/problems/next-permutation/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public void nextPermutation(int[] nums) {
            int n = nums.length;
            int i = n - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) {
                i--;
            }
            if (i >= 0) {
                int j = n - 1;
                while (nums[j] <= nums[i]) {
                    j--;
                }
                swap(nums, i, j);
            }
            reverse(nums, i + 1, n - 1);
        }

        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }

        private void reverse(int[] nums, int left, int right) {
            while (left < right) {
                swap(nums, left++, right--);
            }
        }
    }
}
